package leetcode.Y2024M7;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;

public class S79 {
    String word;

    public boolean exist(char[][] board, String word) {
        int k = 0;
        this.word = word;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (word.charAt(0) == board[i][j]) {
                    boolean res = dfs(board, i, j, k);
                    if (res) return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, int i, int j, int k) {
        if (!judge(board, i, j)) return false;
        if (board[i][j] != word.charAt(k)) return false;
        if (k == word.length() - 1) return true;
        board[i][j] = '\0';
        boolean x = dfs(board, i - 1, j, k + 1);
        boolean y = dfs(board, i + 1, j, k + 1);
        boolean z = dfs(board, i, j - 1, k + 1);
        boolean c = dfs(board, i, j + 1, k + 1);
        board[i][j] = word.charAt(k);
        return x || y || z || c;
    }

    private boolean judge(char[][] board, int i, int j) {
        return i >= 0 && i < board.length && j >= 0 && j < board[0].length ;
    }


    @Test
    public void test() {
        char[][] board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        String word = "ABCCED";
        System.out.println(exist(board, word));
    }
}
